import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

/**
 * Created by forcht on 2018/5/18.
 */
public class Solution {
    public int ladderLength(String start, String end, HashSet<String> dict) {
        int length = 1;
        Queue<String> queue = new LinkedList<>();
        queue.offer(start);
        dict.remove(start);
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size > 0) {
                size--;
                String s = queue.poll();
                if (isDifferentOne(s, end)) return length + 1;
                Iterator<String> iterator = dict.iterator();
                while (iterator.hasNext()) {
                    String str = iterator.next();
                    if (isDifferentOne(s, str)) {
                        queue.offer(str);
                        iterator.remove();
                    }
                }
            }
            length++;
        }
        return 0;
    }

    public boolean isDifferentOne(String a, String b) {
        int count = 0;
        for (int i = 0; i < a.length(); i++) {
            if (a.charAt(i) != b.charAt(i)) {
                count++;
            }
        }
        return count == 1;
    }
}
